﻿// 10081.  道路和航线.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://loj.ac/p/10081

题目描述
原题来自：USACO 2011 Jan. Gold

Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 T 个城镇 ，编号为 1 到 T。
这些城镇之间通过 R 条道路（编号为 1 到 R）和 P 条航线（编号为 1 到 P）连接。每条道路 i 或者航线 i 连接城镇 A_i 到 B_i，花费为 C_i。

对于道路，0 <= C_i <= 10^4，然而航线的花费很神奇，花费 C_i 可能是负数。
道路是双向的，可以从 A_i 到 B_i，也可以从 B_i 到 A_i，花费都是 C_i。然而航线与之不同，只可以从 A_i 到 B_i。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策保证：
如果有一条航线可以从 A_i 到 B_i，那么保证不可能通过一些道路和航线从 B_i 回到 A_i。
由于 FJ 的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。
他想找到从发送中心城镇 S 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

输入格式
第一行为四个空格隔开的整数：T, R, P,S；

第二到第 R+1 行：三个空格隔开的整数（表示一条道路）：A_i, B_i 和 C_i；

第 R+2 到 R+P+1 行：三个空格隔开的整数（表示一条航线）：A_i, B_i 和 C_i。

输出格式
输出 T 行，第 i 行表示到达城镇 i 的最小花费，如果不存在输出 NO PATH。

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

NO PATH
NO PATH
5
0
-95
-100


一共六个城镇。在 1 和 2，3 和 4，5 和 6 之间有道路，花费分别是 5,5,10。同时有三条航线：3\to 5，4\to 6 和 1\to 3，
花费分别是 -100,-100,-10。FJ 的中心城镇在城镇 4。
FJ 的奶牛从 4 号城镇开始，可以通过道路到达 3 号城镇。然后他们会通过航线达到 5 和 6 号城镇。但是不可能到达 1 和 2 号城镇。

数据范围与提示
对于全部数据，1<= T<= 2.5\times 10^4,1<= R,P<= 5\times 10^4,1<= A_i,B_i,S<= T。
保证对于所有道路，0 <= C_i <= 10^4，对于所有航线，-10^4 <= C_i <= 10^4。
*/
int main()
{
    std::cout << "Hello World!\n";
}

 